package codeRandomThoughts.Test188买卖股票的最佳时机IV;

/**
 * 尝试一下一维数组写法
 * 时间复杂度超级低
 */
public class Solution2 {
    public int maxProfit(int k, int[] prices) {
        //dp[i]:i为偶数时,是第i/2次买入时获得的最大利润
        //dp[i]:i为奇数时,是第i/2次卖出时获得的最大利润
        int[] dp = new int[2 * k];

        //初始化
        //第0天 不管完成多少次交易,买入时的利润都是-prices[0]
        for (int i = 0; i < dp.length / 2; i++) {
            dp[2 * i] = -prices[0];
        }

        //从第一天开始递推
        for (int i = 1; i < prices.length; i++) {
            dp[0] = Math.max(dp[0], -prices[i]);
            dp[1] = Math.max(dp[1], dp[0] + prices[i]);

            for (int j = 2; j < dp.length; j += 2) {//我们要两个两个的累加 这样才是一次完整的买入卖出
                dp[j] = Math.max(dp[j], dp[j - 1] - prices[i]);//买入
                dp[j + 1] = Math.max(dp[j + 1], dp[j] + prices[i]);//卖出
            }
        }

        return dp[dp.length - 1];
    }
}
